#include <stdio.h>
#include "12_lib.h"
void sort1(sqlink*);
void sort2(sqlink*,sqlink,sqlink);
void swapSqlink(sqlink* L,sqlink left,sqlink right);
void insertSort(sqlink*);
int BinSearch(sqlink,int,int);
int main(void)
{
	sqlink* l = CreateList();
	PushList(l,1);
	PrintList(l);
	PushList(l,9);
	PushList(l,8);
	PushList(l,6);
	// sort1(l);
	printf("***********sort************\n");
	PrintList(l);
	sqlink last = *l;
	while(last->next != NULL)
	{
		last = last->next;
	}
	// printf("start11 %d; address = %p\n",(*l)->pre->data,NULL);
	printf("***********sort************\n");
	sort2(l,*l,last);
	PrintList(l);
	printf("***********sort************\n");
	insertSort(l);
	PrintList(l);
	printf("***********search************\n");
	printf("%d\n",BinSearch(*l,7,Length(l)));
	printf("%d\n",BinSearch(*l,9,Length(l)));
	printf("%d\n",Length(l));
	PrintList(l);
	return 0;
}
int BinSearch(sqlink l,int value,int length)
{
	int left = 0,right = length,mid = (left + right) / 2,i;
	sqlink l_copy = l;
	while(left <= right)
	{
		mid = (left + right) / 2;
		l_copy = l;
		for(i = 0;i < mid;i++)
		{
			l_copy = l_copy->next;
		}
		// printf("%d\n",l_copy->data);
		if(l_copy->data > value)
		{
			left = mid + 1;
		}
		else if(l_copy->data < value)
		{
			right = mid - 1;
		}
		else
		{
			return 1;
		}
	}
	return -1;
}
void insertSort(sqlink* l)
{
	sqlink new_l = *l;
	*l = new_l->next;
	new_l->next = NULL;
	(*l)->pre = NULL;
	sqlink old_l = *l,new_l_copy = new_l;
	while(old_l != NULL)
	{
		*l = old_l->next;
		while(new_l_copy != NULL)
		{
			if(old_l->data > new_l_copy->data)
			{
				if(new_l_copy->pre != NULL)
				{
					new_l_copy->pre->next = old_l;
				}
				else
				{
					new_l = old_l;
					old_l->pre = NULL;
				}
				new_l_copy->pre = old_l;
				old_l->next = new_l_copy;
				new_l_copy = new_l;
				break;
			}
			else if(new_l_copy->next == NULL)
			{
				new_l_copy->next = old_l;
				old_l->next = NULL;
				old_l->pre = new_l_copy;
				new_l_copy = new_l;
				break;
			}
			new_l_copy = new_l_copy->next;
		}
		old_l = *l;
	}
	*l = new_l;
}
void sort2(sqlink* L,sqlink left,sqlink right)
{
	sqlink key,left_copy = left,right_copy = right;
	int flag_left = 1,flag_right = 1;
	while(left != right)
	{
		while(left != right)
		{
			if(left->data > right->data)
			{
				swapSqlink(L,left,right);
				key = left;
				left = right;
				right = key;
				if(flag_left == 1)
				{
					left_copy = left;
					if(flag_right == 1)
					{
						right_copy = right;
					}
				}
				break;
			}
			else
			{
				flag_right++;
				right = right->pre;
			}
		}
		while(left != right)
		{
			if(left->data > right->data)
			{
				swapSqlink(L,left,right);
				key = left;
				left = right;
				right = key;
				if(flag_right == 1)
				{
					right_copy = right;
				}
				break;
			}
			else
			{
				flag_left++;
				left = left->next;
			}
		}
	}
	// printf("\nleft_copy %d; address = %p\n",left_copy->data,left_copy);
	// printf("right_copy %d; address = %p\n",right_copy->data,right_copy);
	// printf("right %d; address = %p\n",right->data,right);
	// printf("left %d; address = %p\n",left->data,left);
	//printf("left->pre %d; address = %p\n",left->pre->data,left->pre);
	if(left_copy != left->pre && left->pre != NULL && left != left_copy)
	{
		sort2(L,left_copy,left->pre);
	}
	// printf("start %d; address = %p\n",left->data,left);
	if(right_copy != right->next && right->next != NULL && right != right_copy)
	{
		sort2(L,right->next,right_copy);
	}
	// printf("end\n");
	// return left;
}
void swapSqlink(sqlink* L,sqlink left,sqlink right)
{
	// PrintList(L);
	// printf("\tstart %d %d\n",left->data,right->data);
	if(left->pre == NULL)
	{
		*L = right;
	}
	if(left->next == right)
	{
		if(left->pre != NULL)
		{
			left->pre->next = right;
		}
		if(right->next != NULL)
		{
			right->next->pre = left;
		}
		left->next = right->next;
		right->pre = left->pre;
		left->pre = right;
		right->next = left;
	}
	else
	{
		sqlink ll = left->pre,lr = left->next,rl = right->pre,rr = right->next;	
		if(ll != NULL)
		{
			ll->next = right;
		}
		// printf("\tyyy %d %d\n",left->data,right->data);
		lr->pre = right;
		right->pre = ll;
		right->next = lr;
		if(rr != NULL)
		{
			rr->pre = left;
		}
		rl->next = left;
		left->pre = rl;
		left->next = rr;
	}
	// printf("\tend %d %d\n",left->data,right->data);
}
void sort1(sqlink* L)
{
	int length = Length(L);
	sqlink i_temp = NULL;
	for(int i = 0;i < length - 1;i++)
	{
		i_temp = *L;
		// while(l->next != NULL)
		for(int j = 0;j < length - i - 1;j++)
		{
			//printf("%d\n",j);
			if(i_temp->data < i_temp->next->data)
			{
				if(i_temp->pre != NULL)
				{
					i_temp->pre->next = i_temp->next;
				}
				if(i_temp->next->next != NULL)
				{
					i_temp->next->next->pre = i_temp;
				}
				i_temp->pre = i_temp->next;
				i_temp->next = i_temp->next->next;
				if(i_temp->pre != NULL)
				{
					i_temp->pre->next = i_temp;
				}
				if(j == 0)
				{
					*L = i_temp->pre;
					i_temp->pre->pre = NULL;
				}
			}
			else
			{
				i_temp = i_temp->next;
			}
		}
	}
}
